package com.xyhuo.leetcode.january;

/**
 * 寻找旋转排序数组中的最小值
 * https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
 *
 * @time 2024/1/22
 */
public class FindMin {

//    public static void main(String[] args) {
//        FindMin fm = new FindMin();
////        int[] nums = {3, 4, 5, 1, 2};
//        int[] nums = {2, 1};
//        fm.findMin(nums);
//    }

    public int findMin(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }

    private int search(int[] nums, int left, int right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] < nums[left] && nums[middle] < nums[right]) {
            int leftMin = search(nums, left, middle - 1);
            return Math.min(nums[middle], leftMin);
        }
        if (nums[middle] > nums[left] && nums[middle] > nums[right]) {
            return search(nums, middle + 1, right);
        }
        return Math.min(nums[left], nums[right]);
    }
}
